/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package bagtest;

/**
 *
 * @author haoliang.donghl
 */
public class DynamicAlgorithm extends AbstractAlgorithm{
    private static final int CALCULATE_COFF = 10000;

    @Override
    public String getName() {
        return "Dynamic Algorithm";
    }

    @Override
    public void doCalculate() {
        int newCapacity = (int)(capacity * CALCULATE_COFF - 0.5f);
        float[] prev = new float [newCapacity + 1];
        float[] current = new float [newCapacity + 1];
        float[] swaparray;

        for (Item item : items){
            item.setNewSize((int)(item.getSize() * CALCULATE_COFF + 0.5f));
        }

        for (int i = 0; i <= newCapacity; i++){
            prev[i] = 0;
        }

        for (int i = 0; i < items.size(); i++){
            Item item = items.get(i);

            for (int j = 1; j <= newCapacity; j++){
                if (item.getNewSize() <= j){
                    float temp = item.getValue() + prev[j - item.getNewSize()];
                    if (temp > prev[j]){
                        current[j] = temp;
                    }else{
                        current[j] = prev[j];
                    }
                }else{
                    current[j] = prev[j];
                }
            }
            swaparray = prev;
            prev = current;
            current = swaparray;
        }

        this.result = prev[newCapacity];
    }

}
